package 算法.leetcode.array;

import java.util.HashMap;
import java.util.Map;

/**
 * 主要元素
 *
 * 数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。
 *
 * @author lchenglong
 * @date 2020/10/19
 */
public class MajorityElement {

    public static void main(String[] args) {
        int[] nums = new int[]{2,2,1,1,1,2,2};
        System.out.println(majorityElement(nums,1));
    }

    public static int majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        int mid = nums.length/2;
        for (int i=0;i<nums.length;i++) {
            map.put(nums[i],map.get(nums[i])==null?1:map.get(nums[i])+1);
        }
        for (Integer key: map.keySet()) {
            if (map.get(key)>mid) {
                return key;
            }
        }
        return -1;
    }

    /**
     * 哈希表+暴力搜索这种方法无法满足O(1)的空间复杂度，因此需要采用摩尔投票法。
     * 投票法的基本原理是，维护一个众数major和一个频数count，如果出现不同的数count加1，如果出现相同的数，count-1。
     * 最终会发现，如果存在主要元素，那么最终count一定大于0，否则一定不存在主要元素。但仅大于0也不一定能判断确实存在主要元素，
     * 因为如果数组为[4,3,3,2,2,2]，会发现count为2。但是，2并不是主要元素，所以还要添加验证环节。
     *
     * @param nums
     * @param a
     * @return
     */
    public static int majorityElement(int[] nums,int a) {
        if (nums.length == 0){
            return -1;
        } else {
            int count = 0;
            Integer  major = null;
            int mid = nums.length/2;
            for (int i=0;i<nums.length;i++){
                if (count == 0) {
                    major = nums[i];
                    count+=1;
                } else {
                    if (nums[i]!=major) {
                        count-=1;
                    } else {
                        count +=1;
                    }
                }
            }
            if (count >0) {
                int countIdf = 0;
                for (int i=0;i<nums.length;i++){
                    if (nums[i] == major) {
                        countIdf+=1;
                        if (countIdf > mid) {
                            return major;
                        }
                    }
                }
                return -1;
            } else {
                return -1;
            }
        }
    }
}
